package com.liunian.test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class NQueens51 {

	List<List<String>> res = new ArrayList<>();
	public List<List<String>> solveNQueens(int n) {
		char[][] cherryBoard = new char[n][n];
		for (int i = 0; i < n; i++) {
			Arrays.fill(cherryBoard[i], '.');
		}
		backTracking(cherryBoard, 0);
		return res;
	}

	private void backTracking(char[][] cherryBoard, int depth) {
		if (depth == cherryBoard.length) {
			res.add(new ArrayList<>(char2List(cherryBoard)));
			return;
		}
		for (int i = 0; i < cherryBoard.length; i++) {
			if (isValid(cherryBoard, depth, i)) {
				cherryBoard[depth][i] = 'Q';
				backTracking(cherryBoard, depth + 1);
				cherryBoard[depth][i] = '.';
			}
		}
	}

	private List<String> char2List(char[][] cherryBoard) {
		List<String> path = new ArrayList<>();
		for (int i = 0; i < cherryBoard.length; i++) {
			String s = String.copyValueOf(cherryBoard[i]);
			path.add(s);
		}
		return path;
	}

	private boolean isValid(char[][] cherryBoard, int row, int col) {
		for (int i = 0; i < row; i++) {
			if (cherryBoard[i][col] == 'Q') {
				return false;
			}
		}
		for (int i = 0; i < col; i++) {
			if (cherryBoard[row][col] == 'Q') {
				return false;
			}
		}
		for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
			if (cherryBoard[i][j] == 'Q') {
				return false;
			}
		}
		for (int i = row, j = col; i >= 0 && j < cherryBoard.length; i--, j++) {
			if (cherryBoard[i][j] == 'Q') {
				return false;
			}
		}
		return true;
	}

	public static void main(String[] args) {
		NQueens51 nQueens51 = new NQueens51();
		System.out.println(nQueens51.solveNQueens(4));
	}
}
